/**
 * RBTreeTester
 *

/*
 * A tester for the implementation of a red-black tree with integer values
 *
 */

public class RBTreeTester_rand
{

    /**
     * public static boolean isEqual(int[] a, int[] b)
     *
     * preconditions: a != null
     *                b != null
     *
     * returns true if and only if the contents of a and b is the same.
     * This method is used only for testing.
     */
    public static boolean isEqual(int[] a, int[] b) {
        if (a.length != b.length) return false;
        for (int i=0; i<a.length; i++)
            if (a[i] != b[i]) return false;
        return true;
    }
    public static boolean ifExists(int[] a, int elem) {
        for (int i=0; i<a.length; i++)
            if (a[i] == elem) return true;
        return false;
    }
    public static void copyElements(int[] from, int[] to) {

        int index = 0;
        for (int i=0; i<from.length; i++)
            if (from[i] != -1)
            {
                to[index] = from[i];
                index++;
            }
    }

    /**
     * A main routine to test the binary tree routine.
     */

    public static void main(String[] args) {



        boolean insertError = false;
        boolean delError = false;
        boolean containError = false;
        boolean completeError = false;
        boolean maxError = false;
        boolean minError = false;


        for (int maxl = 0; maxl < 30; maxl++)
        {

            int[] elements = new int[maxl];

            int insOrDel = 0;
            int insIndex = 0;
            int elemForInsert = 0;
            int elemNum = 0;
            int elemIndexForDel = 0;


            RBTree t = new RBTree();


            System.out.println("Check for max length = " + maxl);

            for (int i = 0; i < maxl; i++)
            {
                elements[i] = -1;

            }
            for (int i = 0; i < maxl; i++)
            {
                insOrDel = (int) Math.round(Math.random()*3);

                if (insOrDel <=1) //insert
                {
                    elemForInsert = (int) Math.round(Math.random() * maxl*100);

                    if ( ifExists(elements,elemForInsert) == false )
                    {

                        System.out.print("insert("+elemForInsert+") ==> ");
                        elements[insIndex++] = elemForInsert;
                        elemNum++;
                        t.insert(elemForInsert);
                        if ( t.contains(elemForInsert) != true )
                        {
                            System.out.println("t.contains(" + elemForInsert + ") is wrong");
                            containError = true;
                            break;
                        }
                    }
                } else //delete insOrDel == 2
                {
                    elemIndexForDel = (int) Math.round(Math.random() * elemNum);
                    if (elements[elemIndexForDel] != -1)
                    {
                        System.out.print("delete("+elements[elemIndexForDel]+") ==> ");
                        t.delete(elements[elemIndexForDel]);
                        elemNum--;

                        if ( t.contains(elements[elemIndexForDel]) != false )
                        {
                            System.out.println("t.contains(" + elements[elemIndexForDel] + ") is wrong");
                            containError = true;
                            break;
                        }
                        elements[elemIndexForDel] = -1;
                    }
                }



                int[] currElements = new int[elemNum];


                copyElements(elements,currElements);


                java.util.Arrays.sort(currElements);


                int[] treeIntArray = t.toIntArray();

                System.out.print("\n[");    
                for (int j=0; j<treeIntArray.length; j++) System.out.print(" "+treeIntArray[j]); 
                System.out.println(" ]");

                 if ((elemNum > 0) && (t.min() != currElements[0]))
                {
                    System.out.println("minimum is wrong = " + t.min() + " instead of " + currElements[0]);
                    minError = true;
                }
                if ((elemNum > 0) && (t.max() != currElements[elemNum-1]))
                {
                    System.out.println("maximum is wrong = " + t.max() + " instead of " + currElements[elemNum-1]);
                    maxError = true;
                }

                if (elemNum == 5)
                {
                    if (!t.isValid())
                    {
                        System.out.println("wrong: t is valid");   
                        completeError = true;
                    }
                }
                if ( !isEqual(treeIntArray , currElements) )
                {
                    System.out.print("\nError: toIntArray = ( ");
                    for (int j=0; j<treeIntArray.length; j++) System.out.print(" "+treeIntArray[j]); 
                    System.out.println(")");
                    System.out.print("  sorted = (");
                    for (int j=0; j<currElements.length; j++) System.out.print(" "+currElements[j]); 
                    System.out.println(")");
                    if (insOrDel == 0) //after insert
                    {
                        insertError = true;
                    } else //after delete
                    {
                        delError = true;
                    }
                    break;
                }

               
            }
        }

        if (insertError)
        {
            System.out.println("\nError " + 1);
        }
        if (delError)
        {
            System.out.println("\nError " + 2);
        }
        if (completeError)
        {
            System.out.println("\nError " + 3);
        }
        if (maxError)
        {
            System.out.println("\nError " + 4);
        }
        if (minError)
        {
            System.out.println("\nError " + 5);
        }
        if (containError)
        {
            System.out.println("\nError " + 6);
        }
        System.out.println("\n end OF TESTS ");

       
    }

}




